package leetcode;

import java.util.Arrays;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;

/**
 * 756. 金字塔转换矩阵
 *
 * @author K
 * @date 2021/12/6 11:00
 */
public class Solution756 {

    /**
     * 广度优先搜索
     * 报错，更多的组合情况没有考虑到
     */
    public static boolean pyramidTransition(String bottom, List<String> allowed) {
        LinkedList<String> queue = new LinkedList<>();
        combination(bottom, queue);
        Collections.sort(allowed);
        StringBuilder nextBottom = new StringBuilder();
        while (!queue.isEmpty()) {
            String preStr = queue.poll();
            if (!contain(allowed, nextBottom, preStr)) {
                return false;
            }
            if (queue.isEmpty()) {
                bottom = nextBottom.toString();
                if (bottom.length() == 1) {
                    return true;
                }
                nextBottom = new StringBuilder();
                combination(bottom, queue);
            }
        }

        return false;
    }

    private static boolean contain(List<String> allowed, StringBuilder nextBottom, String preStr) {
        for (String element : allowed) {
            if (preStr.equals(element.substring(0, 2))) {
                nextBottom.append(element.substring(2));
                return true;
            }
        }
        return false;
    }

    private static void combination(String bottom, LinkedList<String> queue) {
        for (int i = 0; i < bottom.length()-1; i++) {
            queue.offer(String.valueOf(bottom.charAt(i)) + String.valueOf(bottom.charAt(i + 1)));
        }
    }

    public static void main(String[] args) {
        String bottom = "BCD";
        List<String> allowed = Arrays.asList("BCG", "CDE", "GEA", "FFF");

        String bottom2 = "AABA";
        List<String> allowed2 = Arrays.asList("AAA", "AAB", "ABA", "ABB", "BAC");

        String bottom3 = "CBDDA";
        List<String> allowed3 = Arrays.asList("ACC","ACA","AAB","BCA","BCB","BAC","BAA","CAC","BDA","CAA","CCA","CCC","CCB","DAD","CCD","DAB","ACD","DCA","CAD","CBB","ABB","ABC","ABD","BDB","BBC","BBA","DDA","CDD","CBC","CBA","CDA","DBA","ABA");

//        boolean result = pyramidTransition(bottom, allowed);
//        boolean result2 = pyramidTransition(bottom2, allowed2);
        boolean result3 = pyramidTransition(bottom3, allowed3);
        System.out.println();
    }

}
